1. Field of the Invention
The present invention relates to a shape measuring apparatus designed to radiate a laser beam to an object to be measured, which is held in a capsule especially of a light-transmitting material. The apparatus determines the shape of the object to be measured by making use of a beam reflected from the object. The shape measuring apparatus is ideal for measuring a volume or for CAD input.
Another aspect of the present invention relates to a method and apparatus for obtaining a radial range image of a target object.
Still another aspect of the present invention relates to an image processing method and apparatus and more particularly to a method and apparatus for generating a 3-D geometrical shape using triangular patches.
Yet another aspect of the present invention relates to a 3-D image displaying method and apparatus for displaying a 3-D image by employing a computer.
2. Description of the Related Art
There have been suggested a variety of so-called range finders, which are designed to radiate a beam to a target object (an object to be measured) to determine a distance to the object by taking advantage of the beam reflected from the object and by carrying out two-dimensional optical scan over the entire object, thus obtaining the distance information on the object.
In one method for measuring a distance to an object employed in the aforesaid range finders, an optical pulse is emitted to the object and the distance is determined by measuring the time required for the optical pulse to reflect back from the object In another method, a beam with its intensity modulated into a sine wave is launched into a target object and the distance to the target object is determined by detecting the phase difference between the beam reflected from the object and the original beam. The recent progress in semiconductor lasers and high-frequency circuit technology has enabled these methods to measure distances with a resolution of 1 mm or less and they are used for measuring the position of an object located at a short distance, identifying an object and the like.
There has also been proposed a shape measuring apparatus which is designed to emit a beam from a light source to an object via reflecting mirrors, and at this time, the reflecting mirrors are driven by driving means to two-dimensionally scan the object with the beam in order to detect the changes in the optical path length by utilizing the beam reflected from the object, thus measuring the shape of the object (references: OPTOELECTRONICS (1985, No. 12, pp. 59, by Seiji Inokuchi, et al.).
In the aforesaid shape measuring apparatus, an object to be measured is spatially held or rested. This makes it necessary to have the object undergo two-dimensional optical scanning from restricted directions, presenting a problem in that the rear, top or bottom surface, etc. of the object cannot be measured.
The image distance information obtained by using the shape measuring apparatus described above is referred to as a range image. More specifically, in the range image, the information on depth and position is stored in each picture element position thereof, while in a variable-density image or color image taken by a typical camera or the like, information on brightness is stored in each picture element position thereof. The range image is normally an image measured from a single direction as in the case of photographing with a camera. Hereinafter, this will be referred to as a projective range image. In contrast to the projective range image, a range image provided with the positional information on full circumference directions of a target object is called a radial range image, the positional information being obtained by performing measurement in full circumference directions of the target object.
Conventionally, in order to obtain a radial range image, a range finder for measuring a distance along a single vertical line is fixed around an object to be measured or rotated around it by a fixed rotary system, thereby measuring each line. This conventional method, however, is disadvantageous in that a significantly larger measuring apparatus structure than an object to be measured is required, and the apparatus is hard to move toward the object, leading to poor mobility and high cost.
There are also the following conventional methods available to obtain range images or generate approximate shape data.
(1) A stereoscopic image of a 3-D space such as an indoor scene or a 3-D object can be obtained by photographing them by two cameras, which are installed in parallel with an appropriate distance provided between them, or by moving a single camera in parallel to photograph them twice so that a left image and a right image constituting a stereo image may be obtained. From this stereo image, a 3-D position can be determined according to the principle of triangulation by designating identical points in an actual 3-D space in the right and left images automatically, semi-automatically or manually. By repeating this operation many times, the positions of points in an actual 3-D space can be determined in a 3-D manner.
(2) There is a method available, whereby a range image of a 3-D space such as an indoor scene similar to the one above or a 3-D object can be entered by means of a range imaging apparatus. It is also possible to select an image point from this range image according to some characteristic amount.
(3) It is also possible to enter in order the positions of 3-D points on the surface of a 3-D object by means of a contact or non-contact type 3-D digitizer.
(4) When there are many groups of points, there are methods available, whereby a Delaunay triangulation net is generated using the groups of points as generating points to determine triangles having the points as the vertexes thereof. In one of the methods, points are added one by one to update the Delaunay triangulation net. This method will be described below.
In a Delaunay triangulation net shown in FIG. 12A, when a point marked with x in FIG. 12B is designated, a triangle wherein this point lies in a circumcircle is looked for. When there are three vertexes pj=(xj, yj), pk=(xk, yk), and pl=(xl, yl) of an element triangle in the Delaunay triangulation net, and a determinant shown below is employed for determining whether or not a point p (=(x, y)) to be added is in the circumcircle; ##EQU1##
if, p is a point on a circle, which passes pj, pk, and pl if H(pj,pk,pl,p)=0, or
p is a point in a circle, which passes pj, pk, and pl if H(pj,pk,pl,p)&lt;0, or
p is a point outside a circle, which passes pj, pk, and pl if H(pj,pk,pl,p)&gt;0.
This makes it possible to determine whether the point to be added lies in a circumcircle of the triangle. After making this determination on all triangles, all the triangles, which include the point to be added in the circumcircles, are combined into one area (FIG. 12C). The triangles in this area are deleted, then using the designated point as a vertex, new triangles are generated using two adjoining vertexes of the contour of this area (FIG. 13), and the new triangles are inserted in the area (FIG. 12D).
The prior art (1), (2) or (3) discussed above makes it possible to acquire point positions in a 3-D space such as in an indoor scene or a 3-D object. To restore, however, the 3-D shape of a 3-D space such as in an indoor scene or of a 3-D object, the point positions alone are not sufficient; it is necessary to determine a surface constituted by the points. This was the problem with the prior arts. It was considered possible to generate a Delaunay triangulation net to generate a 3-D geometrical shape based on triangular patches by combining the prior art (4) with the prior arts described above, however, there was no technology available to combine them.
Even if it were possible to combine the prior art (1), (2) or (3) with the prior art (4) and to generate the Delaunay triangulation net, thereby generating the 3-D geometrical shape based on the triangular patches, then the prior art (4) would make it possible to update the triangular patches by updating the Delaunay triangulation net by adding the generating points one after another. If, however, a point is not designated in a correct position, then it is necessary to delete the generating point and update the triangular patches. This was not possible with the prior arts.
There was another problem in addition to the problem described above. When a triangular patch is generated from points by the Delaunay triangulation net, the edges of the triangle are automatically decided according to the principle of Delaunay (the circumcircle principle and the minimal angle maximum principle). There is a need, however, for keeping a line, which connects two given points, as a edge of the triangulation net to be generated, and this need cannot be satisfied.
The following describes a prior art, whereby range image data are obtained, then a resultant image is reproduced and displayed.
Technologies for displaying 3-D images by computer graphics have been developed. The techniques in such image displaying technologies include:
(1) a technique, whereby a shape of an object is described using square lattices fixed equidistantly on a range image to provide the 3-D display; PA1 (2) a technique, whereby adaptive polygon patches, in which the size of polygons are changed in accordance with the curvature of local shape of a curved surface of an object to be displayed, are generated from range image data to describe the shape of the object by the polygon data, thereby providing the 3-D display; PA1 (3) a technique, whereby equidistant square lattices are generated from the shape data of curved surfaces described by a shape modeler to describe the shape of an object, thereby providing the 3-D display; and PA1 (4) a technique, whereby an object is described by an appropriate polygon by a shape modeler to directly use it for the 3-D display.
In the techniques of (1) and (3), however, the shape of the object is described by polygons which have same size; therefore, smaller polygons must be used to represent a complicated surface shape. If, however, more polygons are used, then more than necessary polygons would be used for a uniform surface shape such as a large plane. This results in significant waste in memories used and also it causes other problems, including slow displaying speed.
Likewise, in the techniques of (2) and (4), the size of the polygon is changed in accordance with the surface shape of an object to be displayed; therefore, these techniques are free from the problem with the aforesaid techniques, which use polygons which have same size to represent a shape. Nevertheless, all the four techniques discussed above unavoidably represent details according to shape data even when an observer does not need any detailed shape of the object as in a case, where the observer moves or rotates the object to be displayed. As a result, more load than necessary is applied to a display unit, preventing smooth rotation or movement required by the observer.
In addition, even when the observer does not rotate or move the object, the above techniques attempt to display the details of the shape of the object regardless of the resolution of the display unit or the resolution of the observer's vision even when the object occupies only a small portion of a display screen, i.e., even when the angle of view is small, because of a viewpoint set by the observer. This applies more load than necessary to the display unit.